/**
* class HashMap
** @author Jim
* @version 1.0 
*/

public class HashMap{
	public int CAPACITY = 20;
	public Object[] keys = new Object[CAPACITY];
	public Object[] values = new Object[CAPACITY];
	public String[] status = new String[CAPACITY];
	
	/***Initialize this HashMap object to be empty. 
	 */
	public HashMap(){
		for (int i=0;i<CAPACITY;i++){
			status[i] = "empty";
			keys[i] = "empty";
			values[i] = null;
		}
	}
 
	/***Determines if this object contains no elements
	 **@return true - if this object contains no elements
	 */
	public boolean isEmpty(){ 
		int count = 0; 
		for (int i=0;i<CAPACITY;i++){ 
			if (status[i] == "occup") 
				count++; 
		}
		if (count==0) 
			return true; 
		else 
			return false; 
	}
	
	/***Determines the number of elements **@return the number of elements 
	 */
	public int size(){
		int count = 0; 
		for (int i=0;i<CAPACITY;i++){ 
			if (status[i] == "occup") count++; 
		}
		return count; 
	}
	
	/*** Puts a new key/value pair in this HashMap * Calculates array position from hashcode, and rehashes
	 * if that position is occupied
	 ** @param key - the key to be stored
	 * @param value - the value to be stored 
	 */
	public void put(Object key, Object value){
		int hashcode = Math.abs(key.hashCode()); 
		hashcode %= CAPACITY; 
		System.out.println("Hashcode calculated:" + hashcode);
		if (status[hashcode]=="occup"){ 
			hashcode = rehash(hashcode, 0); 
			System.out.println("Hashcode recalculated:" + hashcode); 
			}
		keys[hashcode] = key; 
		values[hashcode] = value; 
		status[hashcode] = "occup"; 
		}
	
	/*** Checks whether the specifed key is present
	 ** @param key - the key to be checked
	 * @return true - if the key is present
	 */ 
	public boolean containsKey(Object key) {
		boolean found = false;
		for (int i=0; i<CAPACITY; i++){
			if (keys[i]!=null) 
				if (keys[i].equals(key)) 
					found = true; 
		}
		return found; 
	}
	
	/*** Returns the value for a specified key * Uses hashcode to select starting point for search,
	 * and uses linear probing to search from there
	 ** @param key - the key to be found
	 * @return the value associated with key 
	 */ 
	public Object get(Object key) {
		int hashcode = Math.abs(key.hashCode());
		hashcode %= CAPACITY;
		// System.out.println(hashcode);
		int attempts = 0;
		if (keys[hashcode].equals(key)) return
		values[hashcode];
		else{
			while (!keys[hashcode].equals(key) && status[hashcode] != "empty" && hashcode <= CAPACITY && attempts < 10){
				hashcode++;
				if (status[hashcode] == "occup"){
					if (keys[hashcode].equals(key)) 
						return values[hashcode]; 
				}
				else
					attempts++; 
			}
			return null; 
		}
	}
	
	/*** Recursively recalculates an array position to find an * unoccupied position, based on a linear probing method
	 * Checks whether allowed number of attempts has been
	 * exceeded.
	 ** @param hashcode - the hashcode of an object
	 * @param attempts - the number of attempts allowed
	 * @return the new array position
	 */
	private int rehash(int hashcode, int attempts){
		if (hashcode < (CAPACITY) && attempts < CAPACITY){
			hashcode++;
			if (hashcode==CAPACITY) hashcode = 0;
			//System.out.println("rehashing: " + hashcode);
			if (status[hashcode] == "occup"){
				hashcode = rehash(hashcode, attempts+1); 
			}
			return hashcode; 
		}
		else return -1; 
	} 
}